package com.zss.leetcode;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 1.两数之和
 * @author fuguozhang
 * @create 2022/5/9
 */
public class TwoSum {

    public static void main(String[] args) {
        int[] nums = new int[]{1,3,5,7,9};
        int[] tar = twoSum(nums,8);
        Arrays.stream(tar).forEach(System.out::println);

        int[] tar2 = twoSumByHashMap(nums,8);
        Arrays.stream(tar2).forEach(System.out::println);
    }

    /**
     * 暴力破解,时间O(n^2),空间O(1)
     * @param nums
     * @param target
     * @return
     */
    private static int[] twoSum(int[] nums,int target){
        int len = nums.length;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }

    /**
     * hash表，时间复杂度O(n),空间O(n)
     * @param nums
     * @param target
     * @return
     */
    private static int[] twoSumByHashMap(int[] nums,int target){
        HashMap<Integer,Integer> map = new HashMap<>();
        int len = nums.length;
        for(int i=0;i<len;i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }
}
